// https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

// 题干：给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
//       s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。
//       例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。
//       "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
//       返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案

// 示例：输入：s = "barfoothefoobarman", words = ["foo","bar"]
//       输出：[0,9]

// 碎语：我们将s以word[0].size()个一组，接着按照438异位词来求
//       滑动窗口 + 哈希表
//       注意一些不同的地方: 1.哈希表 2.left与right指针的移动步长 3.滑动窗口执行的次数
//       hash[string,int]映射关系如此

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    vector<int> ret;
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        unordered_map<string, int> hash1; // 保存words里面所有单词的频次
        for (const auto& str : words) hash1[str]++;

        int len = words[0].size(), m = words.size();
        for (int i = 0 ; i < len ; i++){ // 执行len次
            unordered_map<string, int> hash2;
            for (int left = i, right = i, count = 0 ; right + len <= s.size() ; right += len){
                // 进窗口 + 维护count
                string in = s.substr(right, len);
                hash2[in]++;
                if (hash2[in] <= hash1[in]) count++;
                // 判断
                if (right - left + len > len * m) {
                    // 出窗口 + 维护count
                    string out = s.substr(left, len);
                    if (hash2[out] <= hash1[out]) count--;
                    hash2[out]--;
                    left += len;
                }
                // 更新结果
                if (count == m) ret.push_back(left);
            }
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    string s = "barfoothefoobarman";
    vector<string> words = {"foo", "bar"};

    vector<int> index = sol.findSubstring(s, words);
    for (const auto& num : index) cout << num << " ";

    return 0;
}